package com.lry.basic.algorithm.common;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/8/26
 */
//        给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
//        示例 1:
//        输入: [1,2,0]
//        输出: 3
//        示例 2:
//        输入: [3,4,-1,1]
//        输出: 2
//        示例 3:
//        输入: [7,8,9,11,12]
//        输出: 1
//        说明:
//        你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
//桶排序
//https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/
public class SmallestNum {
    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{3,4,5,6}));
    }
    public static int firstMissingPositive(int[] nums) {
        int len = nums.length;
        if(null==nums||len==0)return 1;
        //数据预处理 桶排序处理数据
        for(int i=0;i<len;){
            int cur = nums[i];
            //满足这四个条件才可以交换
            if(cur!=i+1&&cur<=len&&cur>0&&cur!=nums[cur-1]){
                //交换 i和cur-1
                nums[i] = nums[cur-1];
                nums[cur-1] = cur;
            }else{
                ++i;
            }
        }
        //找最小正数
        for(int i=0;i<len;++i){
            if(i+1!=nums[i]){
                return i+1;
            }
        }
        // 1 2 3 4这种情况
        return len+1;
    }
}
